๋ฌธ์
๊ฐํธ๋ ์ฝ๋ฉ ๊ต์ก์ ํ๋ ์คํํธ์ ์คํํธ๋งํฌ์ ์ง์ํ๋ค. ์ค๋์ ๊ฐํธ์ ๋ฉด์ ๋ ์ด๋ค. ํ์ง๋ง, ๋ฆ์ ์ ์ ๊ฐํธ๋ ์คํํธ๋งํฌ๊ฐ ์๋ ๊ฑด๋ฌผ์ ๋ฆ๊ฒ ๋์ฐฉํ๊ณ ๋ง์๋ค.
์คํํธ๋งํฌ๋ ์ด F์ธต์ผ๋ก ์ด๋ฃจ์ด์ง ๊ณ ์ธต ๊ฑด๋ฌผ์ ์ฌ๋ฌด์ค์ด ์๊ณ , ์คํํธ๋งํฌ๊ฐ ์๋ ๊ณณ์ ์์น๋ G์ธต์ด๋ค. ๊ฐํธ๊ฐ ์ง๊ธ ์๋ ๊ณณ์ S์ธต์ด๊ณ , ์ด์ ์๋ฆฌ๋ฒ ์ดํฐ๋ฅผ ํ๊ณ G์ธต์ผ๋ก ์ด๋ํ๋ ค๊ณ ํ๋ค.
๋ณดํต ์๋ฆฌ๋ฒ ์ดํฐ์๋ ์ด๋ค ์ธต์ผ๋ก ์ด๋ํ ์ ์๋ ๋ฒํผ์ด ์์ง๋ง, ๊ฐํธ๊ฐ ํ ์๋ฆฌ๋ฒ ์ดํฐ๋ ๋ฒํผ์ด 2๊ฐ๋ฐ์ ์๋ค. U๋ฒํผ์ ์๋ก U์ธต์ ๊ฐ๋ ๋ฒํผ, D๋ฒํผ์ ์๋๋ก D์ธต์ ๊ฐ๋ ๋ฒํผ์ด๋ค. (๋ง์ฝ, U์ธต ์, ๋๋ D์ธต ์๋์ ํด๋นํ๋ ์ธต์ด ์์ ๋๋, ์๋ฆฌ๋ฒ ์ดํฐ๋ ์์ง์ด์ง ์๋๋ค)
๊ฐํธ๊ฐ G์ธต์ ๋์ฐฉํ๋ ค๋ฉด, ๋ฒํผ์ ์ ์ด๋ ๋ช ๋ฒ ๋๋ฌ์ผ ํ๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ง์ฝ, ์๋ฆฌ๋ฒ ์ดํฐ๋ฅผ ์ด์ฉํด์ G์ธต์ ๊ฐ ์ ์๋ค๋ฉด, "use the stairs"๋ฅผ ์ถ๋ ฅํ๋ค.
์ ๋ ฅ
- ์ฒซ์งธ ์ค์ F, S, G, U, D๊ฐ ์ฃผ์ด์ง๋ค. (1 โค S, G โค F โค 1000000, 0 โค U, D โค 1000000) ๊ฑด๋ฌผ์ 1์ธต๋ถํฐ ์์ํ๊ณ , ๊ฐ์ฅ ๋์ ์ธต์ F์ธต์ด๋ค.
์ถ๋ ฅ
- ์ฒซ์งธ ์ค์ ๊ฐํธ๊ฐ S์ธต์์ G์ธต์ผ๋ก ๊ฐ๊ธฐ ์ํด ๋๋ฌ์ผ ํ๋ ๋ฒํผ์ ์์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค. ๋ง์ฝ, ์๋ฆฌ๋ฒ ์ดํฐ๋ก ์ด๋ํ ์ ์์ ๋๋ "use the stairs"๋ฅผ ์ถ๋ ฅํ๋ค.
๐ Logic
class Pair {
int floor;
int cnt;
public Pair(int floor, int cnt) {
this.floor = floor;
this.cnt = cnt;
}
}
- ์ธต ์ ๋ณด์ ๋ฒํผ ๋๋ฅธ ํ์๋ฅผ ์ ์ฅํ๊ธฐ ์ํด
Pairclass๋ฅผ ์์ฑํ๋ค.
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(S, 0));
visited[S] = true;
while(!q.isEmpty()) {
Pair now = q.poll();
int now_floor = now.floor;
int now_cnt = now.cnt;
if (now_floor == G) {
System.out.println(now_cnt);
return;
}
for (int go : upDown) {
int nxFloor = now_floor + go;
if (nxFloor <= 0 || nxFloor > F) continue;
if (visited[nxFloor]) continue;
q.add(new Pair(nxFloor, now_cnt + 1));
visited[nxFloor] = true;
}
}
- ํ์ฌ ์ธต์์ ๋ชฉํ ์ธต๊น์ง ๊ฐ๊ธฐ ์ํด BFS๋ก ์ด๋ ๊ฐ๋ฅํ ์ธต๊ณผ ๋ฒํผ ๋๋ฅธ ํ์๋ฅผ
Queue์ ์ ์ฅํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
class Pair {
int floor;
int cnt;
public Pair(int floor, int cnt) {
this.floor = floor;
this.cnt = cnt;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int F = Integer.parseInt(line[0]), S = Integer.parseInt(line[1]), G = Integer.parseInt(line[2]);
int[] upDown = {Integer.parseInt(line[3]), -Integer.parseInt(line[4])};
boolean[] visited = new boolean[F + 1];
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(S, 0));
visited[S] = true;
while(!q.isEmpty()) {
Pair now = q.poll();
int now_floor = now.floor;
int now_cnt = now.cnt;
if (now_floor == G) {
System.out.println(now_cnt);
return;
}
for (int go : upDown) {
int nxFloor = now_floor + go;
if (nxFloor <= 0 || nxFloor > F) continue;
if (visited[nxFloor]) continue;
q.add(new Pair(nxFloor, now_cnt + 1));
visited[nxFloor] = true;
}
}
System.out.println("use the stairs");
br.close();
}
}
โ๏ธ Review
- BFS ๋ฌธ์ ๋ผ๋ ๊ฒ์ ์๊ณ ํ์ด์ ์์ด๋์ด๋ ๊ธ๋ฐฉ ์ก์๋ ๋ฌธ์ ์ด๋ค. ์๊ณ ๋ฆฌ์ฆ ๋ถ๋ฅ๋ฅผ ์ ๋ณด๊ณ ์์ด๋์ด๋ฅผ ์๊ฐํด๋ด๋ ์ฐ์ต์ด ํ์ํ ๊ฒ ๊ฐ๋ค.
- ์ ๋ฒ๊ณผ ๋์ผํ๊ฒ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ์ ์ฅํ๋ ๋ถ๋ถ์์์ ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๋ฅผ ํผํ ์ ์์๋ค. ์ข ๋ ์์ธํ๊ฒ ์๊ฐํด๋ณด๋ ์ฐ์ต์ด ํ์ํ ๊ฒ ๊ฐ๋ค.